#include "threec.h"

int randInt(int min, int max)
{
    srand(time(0));
    float rand_i = rand();
    return min + (rand_i * (max - min + 1)) / (float)RAND_MAX;
}

#define BLANK '.'

bool isBlankRemain(char* stones)
{
    for (int i = 0; i < 9; i++)
        if (stones[i] == BLANK)
            return 1;
    return 0;
}

bool isPlayerWon(char* stones, char hand)
{
    const int win_pos[8][3] = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } };
    for (int i = 0; i < 8; i++)
        if (stones[win_pos[i][0]] == hand && stones[win_pos[i][0]] == stones[win_pos[i][1]] && stones[win_pos[i][1]] == stones[win_pos[i][2]])
            return true;
    return false;
}

int getBoundWinPos(char* stones, char hand)
{
    for (int i = 0; i < 9; i++)
        if (stones[i] == BLANK) {
            stones[i] = hand;
            if (isPlayerWon(stones, hand)) {
                stones[i] = BLANK;
                return i;
            }
            stones[i] = BLANK;
        }
    return -1;
}

int getStoneNum(char* stones)
{
    int num = 0;
    for (int i = 0; i < 9; i++)
        if (stones[i] != BLANK)
            num++;
    return num;
}

int search(char* stones, char first_hand, char second_hand, char _human_hand, char _mach_hand)
{
    if (isPlayerWon(stones, _mach_hand))
        return 0xf;
    else if (isPlayerWon(stones, _human_hand))
        return -0xf;
    else if (!isBlankRemain(stones))
        return 0;
    int max_value_1 = -0xfff, max_value_2 = 0xfff;
    for (int i = 0; i < 9; i++) {
        if (stones[i] == BLANK) {
            stones[i] = first_hand;
            int score = search(stones, second_hand, first_hand, _human_hand, _mach_hand);
            stones[i] = BLANK;
            if (first_hand == _mach_hand) {
                if (score > max_value_1)
                    max_value_1 = score;
                if (max_value_1 >= max_value_2)
                    return max_value_2;
            } else {
                if (score < max_value_2)
                    max_value_2 = score;
                if (max_value_1 >= max_value_2)
                    return max_value_1;
            }
        }
    }
    if (first_hand == _mach_hand)
        return max_value_1;
    else
        return max_value_2;
}

#define CIRCLE 'O'
#define CROSS 'X'

int think(char* stones, char mach_hand)
{
    char human_hand = mach_hand == CROSS ? CIRCLE : CROSS;
    if (isPlayerWon(stones, mach_hand) || isPlayerWon(stones, human_hand))
        return 0xff;
    else if (!isBlankRemain(stones))
        return -1;
    if (getStoneNum(stones) == 1 && stones[4] == human_hand) {
        const int ways[4] = { 0, 2, 6, 8 };
        return ways[randInt(0, 3)];
    }
    const int boundWinPos = getBoundWinPos(stones, mach_hand);
    if (boundWinPos != -1)
        return boundWinPos;
    int best_score = -0xfff, way_num = -1, ways[8] = {};
    for (int i = 0; i < 9; i++) {
        if (stones[i] == BLANK) {
            stones[i] = mach_hand;
            int score = search(stones, human_hand, mach_hand, human_hand, mach_hand);
            stones[i] = BLANK;
            if (score > best_score) {
                best_score = score;
                way_num = 0;
                for (int j = 0; j < 8; j++)
                    ways[j] = 0;
                ways[0] = i;
            } else if (score == best_score) {
                ways[++way_num] = i;
            }
        }
    }
    return ways[randInt(0, way_num)];
}
